package com.lun.swordtowardoffer2.c14;

public class MinPathSum {
	
	//我写的
	public int minPathSum(int[][] grid) {
		int[][] dp = new int[grid.length][grid[0].length];
		
		for(int i = 0; i < grid.length; i++) {
			for(int j = 0; j < grid[0].length; j++) {
				int incre = 0;
				if(i == 0 && j == 0) {
					//incre = 0;
				}else if(i == 0 && j > 0) {
					incre = dp[i][j - 1];
				}else if(i > 0 && j == 0) {
					incre = dp[i - 1][j];
				}else {
					incre = Math.min(dp[i - 1][j], dp[i][j - 1]);
				}
				dp[i][j] = grid[i][j] + incre;
			}
		}
		
		return dp[grid.length - 1][grid[0].length - 1];
	}
	
	//书上写的
	public int minPathSum2(int[][] grid) {
		int[][] dp = new int[grid.length][grid[0].length];

		dp[0][0] = grid[0][0];
		
		for(int j = 1; j < grid[0].length; j++) {
			dp[0][j] = grid[0][j] + dp[0][j - 1];
		}
		
		for(int i = 1; i < grid.length; i++) {
			dp[i][0] = grid[i][0] + dp[i - 1][0];
			
			for(int j = 1; j < grid[0].length; j++) {
				dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		
		return dp[grid.length - 1][grid[0].length - 1];
	}
	
	//我写的，优化空间
	public int minPathSum3(int[][] grid) {
		int[] dp = new int[grid[0].length];
		
		for(int i = 0; i < grid.length; i++) {
			for(int j = 0; j < grid[0].length; j++) {
				int incre = 0;
				if(i == 0 && j == 0) {
					//incre = 0;
				}else if(i == 0 && j > 0) {
					incre = dp[j - 1];
				}else if(i > 0 && j == 0) {
					incre = dp[j];
				}else {
					incre = Math.min(dp[j], dp[j - 1]);
				}
				dp[j] = grid[i][j] + incre;
			}
		}
		
		return dp[grid[0].length - 1];
	}
	
	
	//书上写的，优化空间
	public int minPathSum4(int[][] grid) {
		int[] dp = new int[grid[0].length];

		dp[0] = grid[0][0];
		
		for(int j = 1; j < grid[0].length; j++) {
			dp[j] = grid[0][j] + dp[j - 1];
		}
		
		for(int i = 1; i < grid.length; i++) {
			dp[0] += grid[i][0] ;
			
			for(int j = 1; j < grid[0].length; j++) {
				dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
			}
		}
		
		return dp[grid[0].length - 1];
	}
	
}
